package com.leetcode.No0016;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * @program: leetcode
 * @description: 最接近的三数之和
 * @author: wangzhihua
 * @date: 2021-12-20
 */
public class Solution {

	@Test
	public void test01() {
		int[] nums = new int[]{4,0,5,-5,3,3,0,-4,-5};
		int target = -2;
		System.out.println(threeSumClosest(nums, target));
	}

	private static int[] array;

	public int threeSumClosest(int[] nums, int target) {
		array = nums;
		Arrays.sort(array);

		int ans = 0;
		int minGap = 100000;
		int len = array.length;
		for (int i = 0; i < len; ++i) {
			for (int j = i + 1; j < len; ++j) {
 				int approximateValue = target - array[i] - array[j];
				int thirdNumIndex;
				if (approximateValue < array[0]) {
					thirdNumIndex = 0;
				} else if (approximateValue > array[len - 1]) {
					thirdNumIndex = len - 1;
				} else {
					thirdNumIndex = findNumIndex(approximateValue, 0, len - 1);
				}
				if (thirdNumIndex <= j) {
					if ((thirdNumIndex = j + 1) >= len) {
						continue;
					}
				}

				int thirdNum = array[thirdNumIndex];

				int gap = Math.abs(thirdNum + array[i] + array[j] - target);
				if (minGap > gap) {
					minGap = gap;
					ans = thirdNum + array[i] + array[j];
				}
			}
		}

		return ans;
	}

	private int findNumIndex(int value, int start, int end) {
		if (end - start <= 1) {
			int leftGap = value - array[start];
			int rightGap = array[end] - value;
			return rightGap > leftGap ? start : end;
		}

		int middle = (start + end) / 2;
		if (value == array[middle]) {
			return middle;
		}
		if (value < array[middle]) {
			return findNumIndex(value, start, middle);
		} else {
			return findNumIndex(value, middle + 1, end);
		}
	}

}
